package BinaryTree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree {
    static class TreeNode{
        public TreeNode left;
        public TreeNode right;
        public char val;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    private TreeNode root;
    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        C.left=F;
        C.right=G;
        E.right=H;
        return A;
    }
    public void preOrder(TreeNode root){
        if(root ==null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }


    public void inOrder(TreeNode root){
        if(root==null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    public void postOrder(TreeNode root){
        if(root==null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }
    //返回值前序遍历
    public List<TreeNode> preOrder2(TreeNode root){
        List<TreeNode> ret = new ArrayList<>();
        if(root==null){
            return ret;
        }
        ret.add(root);
        List<TreeNode> leftTree = preOrder2(root.left);//这里的leftTree就是下一次递归当中的ret，本质上是走完左子树之后，多个retList嵌套
        ret.addAll(leftTree);
        List<TreeNode> rightTree = preOrder2(root.right);//与leftTree同理
        ret.addAll(rightTree);
        return ret;
    }
    public List<TreeNode> inOrder2(TreeNode root){
        List<TreeNode> ret = new ArrayList<>();
        if(root==null){
            return ret;
        }
        List<TreeNode> leftTree = inOrder2(root.left);//这里的leftTree就是下一次递归当中的ret，本质上是走完左子树之后，多个retList嵌套
        ret.addAll(leftTree);
        ret.add(root);
        List<TreeNode> rightTree = inOrder2(root.right);//与leftTree同理
        ret.addAll(rightTree);
        return ret;
    }
    public List<TreeNode> postOrder2(TreeNode root){
        List<TreeNode> ret = new ArrayList<>();
        if(root==null){
            return ret;
        }
        List<TreeNode> leftTree = postOrder2(root.left);//这里的leftTree就是下一次递归当中的ret，本质上是走完左子树之后，多个retList嵌套
        ret.addAll(leftTree);
        List<TreeNode> rightTree = postOrder2(root.right);//与leftTree同理
        ret.addAll(rightTree);
        ret.add(root);
        return ret;
    }
    public int size;
    public void nodeSize(TreeNode root){
        if(root==null){
            return;
        }
        size++;
        nodeSize(root.left);
        nodeSize(root.right);
    }
    public int nodeSize2(TreeNode root){
        if(root==null){
            return 0;
        }
        return nodeSize2(root.left)+ nodeSize2(root.right)+1;
    }
    public int leafSize;
    public void getTheLeafNodeSize(TreeNode root){
        if(root==null){
            return;
        }
        if(root.left==null&&root.right==null){
            leafSize++;
        }
        getTheLeafNodeSize(root.left);
        getTheLeafNodeSize(root.right);
    }
    public int getTheLeafNodeSize2(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            return 1;
        }
        return getTheLeafNodeSize2(root.left)+getTheLeafNodeSize2(root.right);
    }
    public int getKLevelNodeCount(TreeNode root, int k) {
        if(root==null){
            return 0;
        }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+
        getKLevelNodeCount(root.right,k-1);
    }
/*
    public int getHeight(TreeNode root) {
        if(root==null){
            return 0;
        }
        return (getHeight(root.left)>getHeight(root.right)?getHeight(root.left):getHeight(root.right))+1;
    }

 */
    public int getHeight(TreeNode root){
        if(root ==null){
            return 0;
        }
        int leftTree = getHeight(root.left);
        int rightTree = getHeight(root.right);
        return leftTree>rightTree?leftTree+1:rightTree+1;
    }
    public boolean find(TreeNode root, char key) {
        if(root==null){
            return false;
        }
        if(root.val==key){
            return true;
        }
        boolean leftKey = find(root.left,key);
        if(leftKey==true){
            return true;
        }
        boolean rightKey = find(root.right,key);
        if(rightKey==true){
            return true;
        }
        return false;
    }
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return Math.abs(leftHeight-rightHeight)<=1&&isBalanced(root.left)&&isBalanced(root.right);
    }
    public void levelOrder(TreeNode root) {
        if(root==null){
            return ;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.println(cur.val);
            if(cur.left!=null){
                queue.offer(cur.left);
            }
            if(cur.right!=null){
                queue.offer(cur.right);
            }
        }
    }
    public List<List<TreeNode>> levelOrder2(TreeNode root) {
        List<List<TreeNode>> ret = new ArrayList<>();
        if(root==null){
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<TreeNode> re = new ArrayList<>();
            while(size!=0){
                TreeNode cur =queue.poll();
                re.add(cur);
                size--;
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!=null){
                    queue.offer(cur.right);
                }
            }
            ret.add(re);
        }
        return ret;
    }
    public boolean isCompleteTree(TreeNode root) {
        if(root==null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur!=null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else{
                break;
            }
        }
        while(!queue.isEmpty()){
            if(queue.poll()!=null){
                return false;
            }
        }
        return true;
    }
    public boolean isBalanced2(TreeNode root) {
        if(root==null){
            return true;
        }
        return getHeigh(root)>=0;
    }
    public int getHeigh(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeight = getHeigh(root.left);
        int rightHeight = getHeigh(root.right);
        if(leftHeight>=0&&rightHeight>=0&&Math.abs(leftHeight-rightHeight)<=1){
            return Math.max(leftHeight,rightHeight)+1;
        }else{
            return -1;
        }
    }

    public void preorderNor(TreeNode root) {
        if(root==null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode top = null;
        while(cur!=null||!stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            top = stack.pop();
            cur = top.right;
        }
    }

    public void inorderNor(TreeNode root) {
        if(root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode top = null;
        while(cur!=null||!stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.right;
        }
    }

    public void postorderNor(TreeNode root) {
        if(root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode top = null;
        TreeNode pre = null;
        while(cur!=null||!stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            top = stack.peek();
            if(top.right==null||top.right==pre) {
                stack.pop();
                System.out.print(top.val+" ");
                pre = top;
            }else {
                cur = top.right;
            }
        }
    }


    public List<Character> preorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode top = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            top = stack.pop();
            cur = top.right;
        }
        return list;
    }


    public List<Character> postorderTraversal(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        TreeNode cur = root;
        TreeNode top = null;
        TreeNode mark = null;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            top = stack.peek();
            if (top.right == null||top.right==mark) {
                stack.pop();
                list.add(top.val);
                mark = top;
            } else {
                cur = top.right;
            }
        }
        return list;
    }
}
